/*
   @Copyright:LintCode
   @Author:   tjyemail
   @Problem:  http://www.lintcode.com/problem/subarray-sum-closest
   @Language: C++
   @Datetime: 16-02-09 08:38
   */

class Solution {
public:
	/**
	 * @param nums: A list of integers
	 * @return: A list of integers includes the index of the first number 
	 *          and the index of the last number
	 * Tip : prefix sum, prefixsum[i] = sum of range [0,i],
	 *       then sum of subarray range [i,j] = prefixsum[j] - prefix[i-1].
	 *       using pair<sum,id> to record the subsum and index of prefixsum.
	 *       sort it, the neigbour each other may be the closest subsum.
	 */
	vector<int> subarraySumClosest(vector<int> nums){
		// write your code here
		vector<int> ans(2,0);
		if (nums.size()<2) return ans;

		vector<pair<long long,int> > prefixsum;
		long long sum = 0;
		for(int i=0; i<nums.size(); ++i){
			sum += nums[i];
			prefixsum.push_back(make_pair(sum,i));
		}
		sort(prefixsum.begin(),prefixsum.end());
		pair<int,int> p(0,0);
		sum = INT_MAX;
		for(int i=1; i<prefixsum.size(); ++i){
			if (abs(prefixsum[i].first-prefixsum[i-1].first)<sum){
				sum = abs(prefixsum[i].first - prefixsum[i-1].first);
				p.first = min(prefixsum[i-1].second,prefixsum[i].second)+1;
				p.second = max(prefixsum[i-1].second,prefixsum[i].second);
			}
		}
		ans[0] = p.first;
		ans[1] = p.second;
		return ans;
	}
};
